// Package tree
/*

方法1：
时间复杂度：O()
空间复杂度：O()

case1:

r:

*/
package tree

func findDisappearedNumbers(nums []int) []int {
	if nums == nil || len(nums) == 0 {
		return nil
	}
	ret := make([]int, 0)
	n := len(nums)
	// 遇到数字v，则在第v-1的位置处标记一下
	// 标记的方法即为将第v-1处的数字+n
	// 之后再次遍历nums，遇到没有标记的(<=n)，即为缺少的数字
	for _, v := range nums {
		v = (v - 1) % n
		nums[v] += n
	}
	for i, v := range nums {
		if v <= n {
			ret = append(ret, i+1)
		}
	}
	return ret
}
